package com.yoshino.leetcode.improve40.fifteenth;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        // 层序遍历，用null隔开
        Deque<TreeNode> deque = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            deque.offer(null);
            int max = Integer.MIN_VALUE;
            while (deque.peek() != null) {
                TreeNode head = deque.poll();
                if (head.left != null) {
                    deque.offer(head.left);
                }
                if (head.right != null) {
                    deque.offer(head.right);
                }
                max = Math.max(max, head.val);
            }
            deque.poll();
            res.add(max);
        }
        return res;
    }

    public int findBottomLeftValue2(TreeNode root) {
        // 层序 / 深序
        Deque<TreeNode> deque = new LinkedList<>();
        int left = root.val;
        deque.offer(root);
        while (!deque.isEmpty()) {
            deque.offer(null);
            left = deque.peek().val;
            while (deque.peek() != null) {
                TreeNode head = deque.poll();
                if (head.left != null) {
                    deque.offer(head.left);
                }
                if (head.right != null) {
                    deque.offer(head.right);
                }
            }
            deque.poll();
        }
        return left;
    }

    int res = 0;
    int maxDep = -1;
    public int findBottomLeftValue(TreeNode root) {
        // 深序
        dfs(root, 1);
        return res;
    }

    private void dfs(TreeNode root, int dep) {
        if (root.left == null && root.right == null) {
            if (dep > maxDep) {
                maxDep = dep;
                res = root.val;
            }
        }
        if (root.left != null) {
            dfs(root.left, dep + 1);
        }
        if (root.right != null) {
            dfs(root.right, dep + 1);
        }
    }

    List<Integer> list;
    public List<Integer> rightSideView(TreeNode root) {
        list = new ArrayList<>();
        dfsR(root, 1);
        return list;
    }

    private void dfsR(TreeNode root, int dep) {
        if (root == null) {
            return;
        }
        if (list.size() < dep) {
            list.add(root.val);
        }
        dfsR(root.right, dep + 1);
        dfsR(root.left, dep + 1);
    }


}